package java学习.代码随想录.动态规划.背包;

import java.util.Arrays;

/**
 * **************
 * 项目名称: 蓝桥杯-Java学习 <br/>
 * 文件名称:  <br/>
 * 文件描述: 这里添加您的类文件描述，说明当前文件要包含的功能。 <br/>
 * 文件创建：刘世锦Lenovo <br/>
 * 创建时间: 2022/8/22 <br/>
 *
 * @version v1.0 <br/>
 * @update [序号][日期YYYY-MM-DD][更改人姓名][变更描述]<br/>
 * *************
 */
public class 组合总和IV {
    /**
     * 1. 含义：     dp[j] 目标为j的 排列组合数
     * 2. 递推公式：  dp[j] = dp[j]+dp[j-nums[i]]
     * 3. 初始化：   排列组合：dp[0] = 1   求凑成背包容量的最大价值： dp[0]= 0
     * 4. 遍历顺序： 先容量再物品 （排列个数：）
     *    个数不限制使用： 完全背包
     * 5.
     */
    /**
     * 给定一个由正整数组成且不存在重复数字的数组，找出和为给定目标正整数的组合的个数。
     * 示例:
     * nums = [1, 2, 3] target = 4
     * 所有可能的组合为： (1, 1, 1, 1) (1, 1, 2) (1, 2, 1) (1, 3) (2, 1, 1) (2, 2) (3, 1)
     * 请注意，顺序不同的序列被视作不同的组合。
     * 因此输出为 7。
     */
    public static int combinationSum4(int[] nums, int target) {
//      bagsize = target
//      先遍历容量、再遍历物品
        int []dp = new int[target+1];
//  初始化：    求背包容量的最大价值： dp[0]  =0 ;
//      求背包容量的组合数：  dp[0] = 1;
        dp[0] = 1;
        for (int i = 0; i <=target; i++) {
            for (int j = 0; j <nums.length; j++) {
                if ( i>=nums[j]){
                    dp[i] +=dp[i-nums[j]];
                }
            }
        }
//        for (int j = 0; j <=target; j++) {
//            for (int i = 0; i < nums.length; i++) {
//                if ( j>=nums[i]){
//                    dp[j] +=dp[j-nums[i]];
//                }
//            }
//        }
        System.out.println(Arrays.toString(dp));
        return  dp[target];
    }

    public static void main(String[] args) {
         int target = 4 ;
         int[] nums = {1, 2, 3};
        System.out.println(combinationSum4(nums,target));
    }
}
